      1  /**

      2     The sort method of this class sorts an array, using the insertion

      3     sort algorithm.

      4  */

      5  public class InsertionSorter

      6  {

      7     /**

      8        Sorts an array, using insertion sort.

      9        @param a the array to sort

     10     */

     11     public static void sort(int[] a)

     12     {

     13        for (int i = 1; i < a.length; i++)

     14        {

     15           int next = a[i];

     16           // Move all larger elements up

     17           int j = i;

     18           while (j > 0 && a[j - 1] > next)

     19           {

     20              a[j] = a[j - 1];

     21              j--;

     22           }

     23           // Insert the element

     24           a[j] = next;

     25        }

     26     }

     27  }